﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;
using Algoritmia.Problems.Traversals;

namespace Algoritmia.Problems.Topsort
{
    public class Topsorter<T> : ITopsorter<T>
    {
        private readonly Func<IDigraph<T>, IGraphDepthFirstTraverser<T, T>> _createDepthFirstTraverser;

        public Topsorter(Func<IDigraph<T>,IGraphDepthFirstTraverser<T,T>> createDepthFirstTraverser = null)
        {
            _createDepthFirstTraverser = createDepthFirstTraverser ?? (g => new DepthFirstTraverser<T, T>());
        }

        public IEnumerable<T> Topsort(IDigraph<T> g)
        {
            var traverser = _createDepthFirstTraverser(g);
            return traverser.FullTraverse(g, postVisitor: (u, v) => v).Reverse();
        }
    }
}
